﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    public class Prime
    {
        public static bool MillerRabin(long n, int k)
        {
            if (n < 2)
                return false;
            if (n == 2 || n == 3)
                return true;

            long d = n - 1;
            int s = 0;
            while (d % 2 == 0)
            {
                s++;
                d /= 2;
            }
            Random random = new Random();

            for (int i = 0; i < k; i++)
            {
                long a = (long)((n - 4) * random.NextDouble()) + 2;
                long x = 1;
                for (int j = 0; j < d; j++)
                {
                    x *= a;
                    x %= n;
                }
                if (x == 1 || x == -1)
                    continue;

                bool next = false;
                for (int r = 1; r <= s - 1 && !next; r++)
                {
                    x = x * x % n;
                    if (x == 1)
                        return false;
                    if (x == -1)
                        next = true;
                }
                if (!next)
                    return false;
            }
            return true;
        }

        public static bool MillerRabin(long n, long[] a)
        {
            if (n < 2)
                return false;
            if (n == 2 || n == 3)
                return true;

            long d = n - 1;
            int s = 0;
            while (d % 2 == 0)
            {
                s++;
                d /= 2;
            }

            for (int i = 0; i < a.Length; i++)
            {
                long x = 1;
                for (int j = 0; j < d; j++)
                {
                    x *= a[i];
                    x %= n;
                }
                if (x == 1 || x == -1)
                    continue;

                bool next = false;
                for (int r = 1; r <= s - 1 && !next; r++)
                {
                    x = x * x % n;
                    if (x == 1)
                        return false;
                    if (x == -1)
                        next = true;
                }
                if (!next)
                    return false;
            }
            return true;
        }
    }
}
